/*
 * Copyright (C), 2015-2018
 * FileName: Solution017
 * Author:   zhao
 * Date:     2018/11/12 16:11
 * Description: 17. 电话号码的字母组合
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 〈一句话功能简述〉<br>
 * 〈17. 电话号码的字母组合〉
 *
 * @author zhao
 * @date 2018/11/12 16:11
 * @since 1.0.1
 */
public class Solution017 {
    /**************************************
     * 题目
     给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

     给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
     digitToLetter['2']="abc";
     digitToLetter['3']="def";
     digitToLetter['4']="ghi";
     digitToLetter['5']="jkl";
     digitToLetter['6']="mno";
     digitToLetter['7']="pqrs";
     digitToLetter['8']="tuv";
     digitToLetter['9']="wxyz";

     示例:

     输入："23"
     输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
     说明:
     尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
     **************************************/

    /**************************************
     *
     * 想法：
     *      1. 循环0~length-1
     *          将原数组中的值加上当前值得可能性
     *              比如第一个数字2,对应的就是abc，这时候数组中的值就是[a,b,c]
     *              轮到下一个数字3，对应的是def,就把a拼上d/e/f
     *          返回数组
     *      2. 回溯法
     *          把每个数字当作递归的一层，每一层中先枚举一个字母，
     *          递归进入下一层，再删除这个字母，回到上一个状态，枚举下一个字母。
     *          递归结束标志是递归了digits.lengtgh层，即字母组合长度等于digits长度，
     *          递归结束得到一个符合的字母组合，加入list。等于是在循环中套递归
     * 我的做法
     *      超过99%的测试案例
     *      时间复杂度：n2
     *      空间复杂度：n
     * 代码执行过程：
     *
     * 总结：
     *      没有用递归的方式，直接使用迭代的方法
     *
     *
     * ***********************************/
    public List<String> letterCombinations(String digits) {

        if (digits.length() == 0) {
            return Collections.EMPTY_LIST;
        }

        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        char[] chars = digits.toCharArray();
        List<String> result = new ArrayList<>();
        result.add("");

        for (char c : chars) {
            List<String> tmpList = new ArrayList<>();
            String sufStr = map.get(c);
            for (String str : result) {
                for (Character tmpC : sufStr.toCharArray()) {
                    String tmpStr = str + tmpC;
                    tmpList.add(tmpStr);
                }
            }
            result = tmpList;
        }

        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<String> better(String digits) {
        List<String> res = new ArrayList<>();
        String oneRes = "";
        if (digits.equals("")) {
            return res;
        }
        String[] dict = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        int[] digiInt = new int[digits.length()];
        for (int i = 0; i < digits.length(); i++) {
            digiInt[i] = digits.charAt(i) - '0';
        }

        combi(digiInt, 0, dict, res, oneRes);
        return res;
    }

    private void combi(int[] digits, int n, String[] dict, List<String> res, String oneRes) {
        if (n == digits.length) {
            res.add(oneRes);
            return;
        }
        for (int j = 0; j < dict[digits[n]].length(); j++) {
            oneRes = oneRes + dict[digits[n]].charAt(j);
            combi(digits, n + 1, dict, res, oneRes);
            oneRes = oneRes.substring(0, oneRes.length() - 1);
        }
    }
}
